package Sort;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class MySort {
    private static int[] swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
        return array;
    }


    public static void main(String[] args) {
        int[] a = {0, 5, 2, 3, 1, 1};
        oddSort(a);
        System.out.println(Arrays.toString(a));
    }
    //升序
    /**
     * 插入排序
     * 时间复杂度 O(n^2)
     * 空间复杂度 O(1)
     * 稳定性 稳定的算法
     */
    public static void InsertSort(int[] array) {

        //默认j前面的数是有序的
        for (int j = 1; j < array.length; j++) {
            int tmp = array[j];
            int i = j - 1;
            for (; i >= 0; i--) {
                if (array[i] > tmp) {
                    array[i + 1] = array[i];
                } else {
//                    array[i + 1] = tmp;
                    break;
                }
            }
            array[i + 1] = tmp;
        }
    }

    //快排优化
    private static void InsertSort(int[] array, int left, int right) {

        //默认j前面的数是有序的
        for (int j = left + 1; j <= right; j++) {
            int tmp = array[j];
            int i = j - 1;
            for (; i >= 0; i--) {
                if (array[i] > tmp) {
                    array[i + 1] = array[i];
                } else {
                    array[i + 1] = tmp;
                    break;
                }
            }
            array[i + 1] = tmp;
        }
    }


    /**
     * 希尔排序
     * 将数据分为多个组然后用插入排序 通过不断减少数据的组数是数据趋于有序，最后
     * 一次排序的数据已经非常结晶有序了
     * 时间复杂度 O(n^1.3)~O(n^1.5)
     */
    public static void shellSort(int[] array) {
        int gap = array.length;//增量
        while (gap > 1) {
            gap /= 2;
            InsertSortByShell(array, gap);
        }
    }

    private static void InsertSortByShell(int[] array, int gap) {
        //默认j前面的数是有序的
        for (int j = gap; j < array.length; j++) {
            int tmp = array[j];
            int i = j - gap;
            for (; i >= 0; i -= gap) {
                if (array[i] > tmp) {
                    array[i + gap] = array[i];
                } else {
                    break;
                }
            }
            array[i + gap] = tmp;
        }
    }

    /**
     * 选择排序
     * 通过遍历数组找到最小的在放到0位置这样一次类推
     * 时间复杂度 O(n^2)
     * 空间复杂度 O(1)
     * 稳定性 不稳定
     */
    public static void selectSort_better(int[] array) {
        int i = 0;
        int k = array.length - 1;
        while(i <= k){
            int minIndex = i;
            int maxIndex = i;
            for (int j = i; j <= array.length - 1 - i; j++) {
                if (array[minIndex] > array[j]) {
                    minIndex = j;
                }
                if (array[maxIndex] < array[j]) {
                    minIndex = j;
                }
            }
            swap(array, minIndex, i);
            if (maxIndex == i) {
                maxIndex = minIndex;
            }
            swap(array, maxIndex, k);
            i++;k--;
        }
    }

    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int minIndex = i;
            for (int j = i; j <= array.length - 1; j++) {
                if (array[minIndex] > array[j]) {
                    minIndex = j;
                }
            }
            swap(array, minIndex, i);
        }
    }

    /**
     * 堆排序
     * 升序建立大堆1，降序建立小堆
     * 建立大队 向下交换
     * 大堆建立，递归写法
     * 大堆的根节点root是最大的，这样就找到了最大的元素，把这个元素poll出去储存，最后数据就有序了
     * 时间复杂都 O(N*logN)
     * 空间复杂度 O(N)
     * 稳定性 不稳定
     */

    public static void heapSort(int[] array) {

        int useSize = array.length;//这个是下表的最后元素

        while (useSize > 0) {
//            SortHeapMain(array, 0, useSize);//最大的在0
            creatHeap(array,useSize);//创建大根堆，创建一次找到一个最大值
            swap(array, 0, useSize-1);//这个是最后元素的下表
            useSize--;
        }
    }

    public static void creatHeap(int[] array,int userSize) {
        for (int i = array.length - 1; i >= 0; i--) {//每个元素都要遍历
            shiftDown(array,i, userSize);
        }
    }

    private static void shiftDown(int[] array,int parent, int userSize) {
        int child = parent * 2 + 1;//这个是父节点的左节点
        while (child < userSize) {
            //和大的交换
            if ((child+1) < userSize && array[child] < array[child + 1]) {
                child++;//走到更大的右节点
            }
             if (array[child] > array[parent]) {//交换
                swap(array, child, parent);
                parent = child;
                child = child*2+1;//走到写一个左节点
            }else {//说明调整好了
                break;
            }
        }
    }

    private static void SortHeapMain(int[] array,int parent,int useSize) {
        //左支树
        int child = parent * 2 + 1;

        if (child >= useSize) {
            return;
        }

        //交换
        if (child + 1 < useSize && array[child] < array[child + 1]) {//左支树小于右支树
            child++;
        }

        if (array[parent] < array[child]) {
            swap(array, parent, child);
        }

        parent = child;//走到下一个支点

        SortHeapMain(array, parent,useSize);
    }

    /**
     * 冒泡排序
     * 时间复杂度 O(n^2)
     * 空间复杂度 O(1)
     * 稳定性 稳定
     */
    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            boolean flg = true;
            for (int j = i+1; j < array.length; j++) {
                if (array[j] < array[i]) {
                    swap(array, j, i);
                    flg = false;
                }
            }
            if (flg) {
                return;
            }
        }
    }

    /**
     * 快速排序
     * 通过不断将数组分为一半一半并对一半进行局部排序最后达到数据整体有序
     * 时间复杂度 O(NlogN)
     * 空间复杂度 O(logN) 最长的一棵树的长度
     * 稳定性 不稳定
     */
    public static void quickSort(int[] array) {
        quickSortMain(array,0,array.length - 1);
    }

    private static void quickSortMain(int[] array, int left, int right) {
        if (right <= left) {
            return;
        }

        //优化
        // 1 三数取中 保证不会递归很深导致栈溢出
//        getMiddle(array,left,right);

        // 2 递归到小区间时使用插入排序
        if (right - left < 7) {
            InsertSort(array, left, right);
            return;
        }

        //以array[left]为基准，吧数组分开 放回中点的下标
        int middle = separate_hoare(array, left, right);

        //递归
        //左边
        quickSortMain(array, left, middle - 1);
        //右边
        quickSortMain(array, middle + 1, right);
    }

    //Hoare
    private static int separate_hoare(int[] array, int left, int right) {
        int pivot = array[left];
        int tmp = left;
        while (right != left) {
            //从右边找到比pivot小的数
            while (right > left && array[right] >= pivot) {
                right--;
            }

            //从左边找到比pivot大的数
            while (right > left && array[left] <= pivot) {
                left++;
            }

            swap(array, left, right);
        }
        swap(array, tmp, left);

        return left;
    }

    //挖坑法 将pivot储存在tmp中，直接吧值覆盖在原数据上
    private static int separate_dig(int[] array, int left, int right) {
        //优化 三数取中 保证不会递归很深导致栈溢出
//        getMiddle(array,left,right);
        int pivot = array[left];
        while (left != right) {
            //走右边
            while (left < right && array[right] >= pivot) {
                right--;
            }
            //直接填入
            array[left] = array[right];

            //左边
            while (left < right && array[left] <= pivot) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = pivot;

        return left;
    }

    //双指针法
    private static int separate_index(int[] array, int left, int right) {
        int d = left + 1;
        int pivot = array[left];
        for (int i = left + 1; i <= right; i++) {
            if (array[i] < pivot) {
                swap(array, i, d);
                d++;
            }
        }
        swap(array, d - 1, left);

        return d - 1;
    }

    private static void getMiddle(int[] array, int left, int right) {
        int middle = (left + right) / 2;
        if (array[left] < array[middle] && array[middle] < array[right]//取m
        || array[right] < array[middle] && array[middle] < array[left]) {
            swap(array,left, middle);
        } else if (array[middle] < array[right] && array[middle] < array[left]//去right
                || array[left] < array[middle] && array[right] < array[middle]) {
            swap(array, left, right);
        } else {
            return;
        }

    }

    /**
     * 归并排序
     * 使用分治法，将数组中的元素递归到只剩一个 再回归并对数据进行排序
     * 排序时是创建一个新数组，将数据储存到新数组中最后在拷贝
     * 对于海量数据的排序问题可以使用 他会开辟新的空间去储存有序的数据
     * 不会吧所有的数据一下都在内存上进行排序，而是将数据分成很多份分别
     * 进行排序，把有序的数据放到硬盘上，最后就整体有序了
     * 不能使用copyOf因为要对原数组进行一定范围内的拷贝
     * --
     * 时间复杂度 O(NlogN)
     * 空间复杂度 O(N)
     * 稳定性 稳定
     */
    public static void mergeSort(int[] array) {mergeSortMain(array,0,array.length-1);}

    private static void mergeSortMain(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }

        int middle = (right + left) / 2;

        //递归 吧数递归为单独的数
        mergeSortMain(array, left, middle);//左
        mergeSortMain(array, middle+1, right);//右

        //合并
        merge(array,middle, left, right);
    }

    //创建一个新的数组，再把新的数组的数拷贝到老的数组
    private static void merge(int[] array, int middle, int left, int right) {
        int[] newArray = new int[right - left + 1];
        int i = 0;
        //左边的数组
        int s1 = left;
        int e1 = middle;
        //右边的数组
        int s2 = middle + 1;
        int e2 = right;

        //排序
        while (s1 <= e1 && s2 <= e2) {
            if (array[s1] < array[s2]) {
                newArray[i++] = array[s1];
                s1++;
            } else {
                newArray[i++] = array[s2];
                s2++;
            }
        }
        while (s1 <= e1) {//s1没有拍完
            newArray[i++] = array[s1++];
        }

        while (s2 <= e2) {//s2没有拍完
            newArray[i++] = array[s2++];
        }
        //将数组拷贝到老数组

        i = 0;
        for (int j = left; j <= right; j++) {
            array[j] = newArray[i++];
        }

    }

    /**
     * 计数排序
     * 非基于比较的排序
     * 将不同的数以下表的方式储存，在挨个遍历数组打印
     * 适用与一定范围内的数据
     * 时间复杂度 O(N)
     * 空间复杂度 O(N)
     * 稳定性 不稳定
     * @param array
     */
    public static void countSort(int[] array) {
        int min = array[0];
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] < min) {
                min = array[i];
            }
            if (array[i] > max) {
                max = array[i];
            }
        }
        countSortMain(array,min,max);
    }

    public static void countSortMain(int[] array, int min, int max) {
        int[] newArray = new int[max - min + 1];

        //遍历array
        for (int j : array) {
            newArray[j - min]++;
        }

//        //打印newArray
//        for (int j = 0 ; j < array.length;j++) {
//            while (j < array.length && newArray[j] > 0) {
//                System.out.print((j + min) + " ");
//                newArray[j]--;
//            }
//        }
        //拷贝
        int i = 0;
        for (int j = 0 ; j < array.length;j++) {
            while (newArray[j] > 0) {
//                System.out.print((j + min) + " ");
                array[i++] = j + min;
                newArray[j]--;
            }
        }
    }

    /**
     * 基数排序
     * 找到最大数据，需要插入的次数为最大数据的位数
     * 使用10个队列分别编号为1-10，先以个位数来插入对应的队列，然后再从对头挨个出元素
     * 再以十位数，再从对头挨个出元素，再以百位数...直到最大数据的每位数都入了队列
     * 这样就排好序了
     */
    public static void oddSort(int[] array) {
        //创建10个队列
        Queue<Integer>[] queues = new Queue[10];
        for (int i = 0; i < 10; i++) {
            queues[i] = new LinkedList<Integer>();
        }
        //找到最大的数
        int max = array[1];
        for (int i = 1; i < array.length; i++) {
            max = Math.max(max, array[i]);
        }
        int times = 0;//决定这次循环比较的是哪位数
        while (max != 0) {
            for (int i = 0; i < array.length; i++) {//遍历则这个数组
                int tmpVal = array[i];
                for (int j = 0; j < times; j++) {//决定比较哪位数
                    tmpVal /= 10;
                }
                int index = tmpVal % 10;//根据该为数来选择插入哪个队列
                queues[index].add(array[i]);
            }
            //重新为这个数组排序
            int indexArr = 0;
            for (Queue<Integer> tmp : queues) {
                while (!tmp.isEmpty()) {
                    array[indexArr++] = tmp.poll();
                }
            }
            times++;
            max /= 10;
        }
    }
}


